#include <cstdio>

int s[ 1001 ];

int find( int root )
{
    if ( s[ root ] == -1 )
        return root;
    return s[ root ] = find( s[ root ] );
}

bool map[ 1001 ][ 1001 ];

int main( )
{
    int  i, j, a, b, m, n;
    bool cor;
    while ( scanf("%d", &n) != EOF && n )
    {
        cor = true;
        scanf("%d", &m);
        for ( i = 1; i <= n; i++ )
        {
            s[ i ] = -1;
            for ( j = 1; j <= n; j++ )
                map[ i ][ j ] = false;
        }
        for ( i = 0; i < m; i++ )
        {
            scanf("%d%d", &a, &b);
            if ( a == b )
                continue;
            map[ a ][ b ] = map[ b ][ a ] = true;
            a = find( a );
            b = find( b );
            if ( a != b )
                s[ a ] = b;
        }
        for ( i = 2; i <= n; i++ )
            if ( find( i ) != find( i - 1 ) )
            {
                cor = false;
                break;
            }
        for ( i = 1; i <= n; i++ )
        {
            a = 0;
            for ( j = 1; j <= n; j++ )
                a += map[ i ][ j ];
            if ( a & 1 )
            {
                cor = false;
                break;
            }
        }
        if ( cor )
            puts("1");
        else
            puts("0");
    }
    return 0;
}
